//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 
//
// 示例 1: 
//
// 输入: "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 输入: "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// 
//
// 示例 3: 
//
// 输入: "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
// Related Topics 哈希表 双指针 字符串 Sliding Window 
// 👍 4258 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.HashMap;
import java.util.Map;

/**
 * Java：无重复字符的最长子串
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P3_LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new P3_LongestSubstringWithoutRepeatingCharacters().new Solution();
        MyUtil.print(solution.lengthOfLongestSubstring("pwwkew"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 以i位置为结尾的子串无重复的最大长度
     * T: O(n)
     * S: O(n)
     */
    class Solution {
        public int lengthOfLongestSubstring(String str) {
            if (str == null || str.length() == 0) {
                return 0;
            }
            int N = str.length();
            // 上次出现的位置
            Map<Character, Integer> map = new HashMap<>();
            char[] strs = str.toCharArray();
            // dp[i]: 以i位置为结尾的子串无重复的最大长度
            int[] dp = new int[N];
            dp[0] = 1;
            map.put(strs[0], 0); // 加入0位置
            int max = dp[0];
            for (int i = 1; i < N; i++) {
                int min = dp[i - 1] + 1;
                // 最短为准
                if (map.containsKey(strs[i])) {
                    min = Math.min(min, i - map.get(strs[i]));
                }
                map.put(strs[i], i);
                dp[i] = min;
                max = Math.max(max, min);
            }
            return max;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}